package com.dl.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author DL
 * @create 2023-06-02 9:14
 */
public class LeetcodeTest {
    public static void main(String[] args) {
        System.out.println(1);

    }


    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    public int[] twoSum2(int[] nums, int target) {
        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        String target = String.valueOf(x);
        String reverse = new StringBuilder(target).reverse().toString();
        return reverse.equals(target);
    }

    public boolean isPalindrome2(int x) {
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }


    // 最长公共前缀
    // List<String> list = Arrays.stream(strs).sorted(Comparator.comparingInt(String::length)).collect(Collectors.toList());
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs, Comparator.comparingInt(String::length));
        int min = strs[0].length();
        int j = 1;

        while (j <= min) {
            for (String str : strs) {
                if (!str.startsWith(strs[0].substring(0, j))) {
                    return strs[0].substring(0, j - 1);
                }
            }
            j++;
        }
        return strs[0];
    }

    public String longestCommonPrefix2(String[] strs) {
        int len = strs.length;
        // 空数组
        if (len == 0) {
            return "";
        }
        // 数组中只有一个字符串时
        if (len == 1) {
            return strs[0];
        }
        //先默认第一个字符串为公共前缀 然后依次减少一个字符比较
        String sPrefix = strs[0];
        // 否则依次比较判断 选第一个字符串与剩下的依次比较
        for (int i = 1; i < len; i++) {
            // 当与后面的字符串匹配不符合时，截取s_prefix
            // 如果与第二个没有匹配到前缀，后面的字符串就不要再匹配了
            if (!strs[i].startsWith(sPrefix)) {
                sPrefix = sPrefix.substring(0, sPrefix.length() - 1);
                i--;
            }
        }
        return sPrefix;
    }

    // 有效的括号
    public boolean isValid(String s) {
        char[] stack = new char[s.length()]; // 数组模拟栈
        int top = -1;// 栈顶指针
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack[++top] = ')';// 遇到左括号在栈顶加入对应的右括号，++模拟入栈
            } else if (c == '[') {
                stack[++top] = ']';
            } else if (c == '{') {
                stack[++top] = '}';
            } else if (top == -1 || stack[top--] != c) {//之前没有对应的左括号或者左右括号不匹配，--模拟出栈
                return false;
            }
        }
        return top == -1;//判断是否有剩余的左括号没有被匹配
    }


    // 反转链表
/*    public ListNode reverseList(ListNode head) {
        // 如果当前要反转的节点为 null 或者反转链表为 null
        // head.next 为 null，即反转链表的尾结点不存在，即反转链表不存在
        if (head == null || head.next == null) return head;
        // 节点 p 其实就是反转链表的头节点
        ListNode p = reverseList(head.next);
        // 我们将反转链表的尾结点（head.next）的 next 指向当前即将反转的节点
        head.next.next = head;
        // 然后让当前节点变成反转链表的尾结点
        head.next = null;
        // 返回反转链表的头结点
        return p;
    }*/

}
